package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.base.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class BinaryTreeLevelOrderTraversal2 {

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        levelOrderBottom(root, 0, res);
        int size = res.size();
        for (int i = 0; i < size / 2; ++i){
            int target = size - i - 1;
            List<Integer> list = res.get(i);
            res.set(i, res.get(target));
            res.set(target, list);
        }
        return res;
    }

    public void levelOrderBottom(TreeNode root, int level, List<List<Integer>> res){
        if (root == null){
            return;
        }
        while (level >= res.size()){
            res.add(new ArrayList<>());
        }
        res.get(level).add(root.val);
        levelOrderBottom(root.left, level + 1, res);
        levelOrderBottom(root.right, level + 1, res);
    }

    public static void main(String[] args) {
        TreeNode root = TreeNode.buildTree(3,9,20,null,null,15,7);
        List<List<Integer>> lists = new BinaryTreeLevelOrderTraversal2().levelOrderBottom(root);
        System.out.println(lists);
    }
}
